class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int length = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        for(int first = 0;first < length;first++) {
            if(first > 0 && nums[first] == nums[first-1]) {
                //和上一个相同，不在进行遍历
                continue;
            }
            int third = length-1;
            int target = -nums[first];

            for(int second = first+1;second < length;second++) {
                if(second > first+1 && nums[second] == nums[second-1]) {
                    continue;
                }
                while(second < third && nums[second] + nums[third] > target) {
                    third--;//使得third在second的右边，而且存在可能值等于0
                }
                if(second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    lists.add(list);
                }
            }
        }
        return lists;
    }
}